package class23.test;

public class Code01_SplitSumClosed {

    public static int splitSumClosed(int[] arr){
        if(arr == null || arr.length < 2){
            return 0;
        }
        int sum = 0;
        for (int i = 0; i < arr.length; i++) {
            sum+= arr[i];
        }
        sum = sum / 2;

        int res = process(arr,0,sum);
        return res;
    }

    private static int process(int[] arr, int index, int rest) {
        if(index == arr.length){
            return 0;
        }else {
            int res = 0;
            int exist = process(arr, index + 1, rest);
            if (rest >= arr[index]) {
                res += arr[index] + process(arr, index + 1, rest - arr[index]);
            }
            return Math.max(exist, res);
        }
    }

    public static void main(String[] args) {
        int[] arr = new int[]{4,1,3,5,8};
        System.out.println(splitSumClosed(arr));
        System.out.println(bp(arr));

    }

    public static int bp(int[] arr){
        if(arr == null || arr.length<0){
            return 0;
        }
        int rest = 0;
        for (int i : arr) {
            rest += i;
        }
        rest = rest / 2;
        int[][] bp = new int[arr.length+1][rest + 1];
        for (int index = arr.length-1; index >= 0; index --) {
            for (int rest2 = 0; rest2 <= rest; rest2++) {
                int res = 0;
                int exist = bp[index+1][rest2];
                if (rest2 >= arr[index]) {
                    res += arr[index] + bp[index+1][rest2-arr[index]];
                }
                bp[index][rest2] = Math.max(exist, res);
            }
        }
        return bp[0][rest];
    }
}
